package basic.courseLearn07.problem;

import basic.courseLearn07.Graph;
import basic.courseLearn07.Node;
import org.junit.Test;

import java.util.HashMap;
import java.util.HashSet;

//拓扑排序
public class TopologicalSort {

    public void sort(Graph graph){
        //1. 定义size，存放节点个数；set，存放已输出节点；
        int size = 0;
        HashSet<Node> set = new HashSet<>();
        //2. while循环，直至所有节点输出
        while (size < graph.getNodes().size()) {
            for (Node node : graph.getNodes().values()) {
                if (node.in==0 && !set.contains(node)){
                    System.out.print(node.value + " ");
                    set.add(node);
                    size++;
                    for (Node next : node.nexts) {
                        next.in--;
                    }
                }
            }
        }
    }

    @Test
    public void test(){
        Graph graph = new Graph();
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        Node node5 = new Node(5);
        Node node6 = new Node(6);
        Node node7 = new Node(7);

        node1.getNexts().add(node3);
        node1.in=0;
        node2.getNexts().add(node3);
        node2.in=0;
        node3.getNexts().add(node4);
        node3.getNexts().add(node6);
        node3.in=2;
        node6.getNexts().add(node7);
        node6.in=1;
        node7.getNexts().add(node4);
        node7.in=1;
        node4.getNexts().add(node5);
        node4.in=2;
        node5.in=1;

        HashMap<Integer, Node> map = new HashMap<>();
        map.put(1, node1);
        map.put(2, node2);
        map.put(3, node3);
        map.put(4, node4);
        map.put(5, node5);
        map.put(6, node6);
        map.put(7, node7);
        graph.setNodes(map);

        sort(graph);

    }









}
